Міністерство Освіти і Науки України Національний Університет “Львівська Політехніка”
Кафедра ЕОМ Конспект лекцій з курсу “Дискретна математика”для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” Затвердженона засіданні кафедриЕлектронних Обчислювальних МашинПротокол №  від Львів – 2007  Конспект лекцій  з курсу “Дискретна математика” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” / Укладач: Р. Попович – Львів: Національний університет “Львівська політехніка”, 2007, с. Укладач: Р. Попович, к.т.н., доцент Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри ЕОМ Рецензенти:  Елементи теорії множин Вступ Дискретна математика є розділом математики, що зародилася в давні часи. Її головною відмінністю є дискретність, тобто антипод неперервності. Дискретна математика включає традиційні розділи математики, які вже сформувалися (математичну логіку, алгебру, теорію чисел), і нові, що інтенсивно розвиваються. У більш як двотисячорічній історії дискретної математики сучасний період є одним із найінтенсивніших періодів її розвитку: дуже швидко розширюється сфера застосування, інтенсивно зростають обсяги нової інформації та кількість нових результатів. Якщо ще порівняно недавно ця наука була сферою інтересів лише вузького кола фахівців, то тепер вона перетворюється на наукову дисципліну, дуже важливу й потрібну для багатьох, а у сфері сучасної освіти – для всіх. Масове використання обчислювальної техніки та інформаційних технологій значно розширює сферу прикладних досліджень, у яких все більше застосовується апарат дискретної математики. Базовим розділом як дискретної математики, так і взагалі всієї математики, є теорія множин. Коротка історична довідка Основи теорії множин були закладені відомим німецьким математиком Георгом Кантором у другій половині минулого століття. Поява теорії множин була зустрінута з ентузіазмом багатьма авторитетними математиками. Вони побачили в ній можливість створення метамови математики, тобто формальної одностайної системи понять і принципів, за допомогою якої можна було б викласти з єдиних позицій зміст різноманітних традиційно далеких один від одного розділів математики. Перші такі досить успішні спроби були виконані вже незабаром після виникнення канторівської теорії множин. Однак пізніші дослідники виявили в теорії Кантора чимало суперечностей: так званих парадоксів або антиномій теорії множин. Виникла кризова ситуація. Одна частина математиків, посилаючись на штучність сформульованих антиномій, вважала за краще не помічати ці суперечності або не надавати їм великого значення. У той час як інша (скажімо, відповідальніша) група математиків зосередила свої зусилля на пошуках більш обгрунтованих та точних принципів і концепцій, на яких могла б бути побудована несуперечлива теорія множин. У результаті було запропоновано кілька формальних (або аксіоматичних) систем, які служать фундаментом сучасної теорії множин, а значить, фундаментом всієї класичної математики. Важливість цих досліджень серед іншого підкреслює той факт, що значний внесок у становлення аксіоматичної теорії множин зробили такі видатні математики і мислителі XX століття, як Б.Рассел, Д.Гільберт, К.Гедель та ін. Сьогодні теорія множин - це математична теорія, на якій грунтується більшість розділів сучасної математики, як неперервної, так і дискретної. Поняття множини. Способи задання множин Для наших цілей достатньо буде викладення основ так званої інтуїтивної або наївної теорії множин, яка в головних своїх положеннях зберігає ідеї та результати засновника теорії Г.Кантора. В інтуїтивній теорії множин поняття "множина" належить до первинних невизначальних понять, тобто воно не може бути означено через інші більш прості терміни або об’єкти, а пояснюється на прикладах, апелюючи до нашої уяви та інтуіції. Такими поняттями в математиці є також поняття "число", "пряма", "точка", "площина" тощо. Канторівський вираз: "Множина - це зібрання в єдине ціле визначених об’єктів, які чітко розрізняют...